/*
 * @Author: liusheng
 * @Date: 2022-04-29 11:33:25
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-29 16:35:18
 * @Description: 剑指 Offer II 049. 从根节点到叶节点的路径数字之和
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 剑指 Offer II 049. 从根节点到叶节点的路径数字之和
给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

 

示例 1：
          1
         / \
        2   3

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
示例 2：
          4
         / \
        9   0
       / \  
      5   1   

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026
 

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10
 

注意：本题与主站 129 题相同： https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

通过次数12,918 提交次数17,326
 */

#include "header.h"
#include <functional>
// Definition for a binary tree node.
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        list<int> digits;
        int totalSum = 0;
        traversePreorderSum(root,digits,totalSum);
        return totalSum;
    }
private:
    void traversePreorderSum(TreeNode * root,list<int> & digits,int & totalSum)
    {
        if (!root)
        {
            return;
        }

        digits.push_back(root->val);

        if (!root->left && !root->right)
        {
            int sum = 0;
            auto iter = digits.begin();
            while (iter != digits.end())
            {
                // printf("*iter:%d\n",*iter);
                sum = sum * 10 + *iter;
                ++iter;
            }

            totalSum += sum;
            // printf("totalSum:%d,sum:%d\n",totalSum,sum);
            //after caculate,pop the last element
            if (!digits.empty())
            {
                digits.pop_back();
            }
            return;
        }
               
        traversePreorderSum(root->left,digits,totalSum);
        traversePreorderSum(root->right,digits,totalSum);

        //after traverse left and right,this tree has been traversed
        //so pop the tree's value
        if (!digits.empty())
        {
            digits.pop_back();
        }
    }
};

/*
preorder dfs solution
*/
class Solution2 {
public:
    int sumNumbers(TreeNode* root) {
        return traversePreorderSum(root,0);
    }
private:
    int traversePreorderSum(TreeNode * root,int prevSum)
    {
        if (!root)
        {
            return 0;
        }

        int sum = prevSum * 10 + root->val;
        if (!root->left && !root->right)
        {
            return sum;
        }
               
        int left = traversePreorderSum(root->left,sum);
        int right = traversePreorderSum(root->right,sum);

        return left + right;
    }
};

/*
same as above,use lambda function
*/
class Solution3 {
public:
    int sumNumbers(TreeNode* root) {
    //capture list should be &,otherwise can't call itself in lambda,must be use function declare,auto deduced 
    //is failed for Line 28: Char 20: error: variable 'traversePreorderSum' declared with 
    //deduced type 'auto' cannot appear in its own initializer
        function<int (TreeNode *,int)> traversePreorderSum = [&] (TreeNode * root,int preSum) ->int {
            if (!root)
            {
                return 0;
            }
            
            int sum = preSum * 10 + root->val;
            if (!root->left && !root->right)
            {
                return sum;
            }
            
            return traversePreorderSum(root->left,sum) + traversePreorderSum(root->right,sum);
        };
        
        return traversePreorderSum(root,0);
    }
};

/*
BFS solution:use nodeQ to BFS traverse by level,use sumQ to record
the traverse node's value,only add it to sum when it's a leafnode
*/
class Solution4 {
public:
    int sumNumbers(TreeNode* root) {
        queue<TreeNode *> nodeQ;
        queue<int> sumQ;//the node's corresponding sum
        
        nodeQ.push(root);
        sumQ.push(root->val);
        
        int totalSum = 0;
        //bfs traverse level by level
        //only add the sum when it's leaf node
        while (!nodeQ.empty())
        {
            TreeNode * node = nodeQ.front();
            nodeQ.pop();
            
            int sum = sumQ.front();
            sumQ.pop();
            
            if (!node->left && !node->right)
            {
                totalSum += sum;
            }
            
            //push node->left to nodeQ
            //and push it's corresponding value to sumQ 
            if (node->left)
            {
                nodeQ.push(node->left);
                sumQ.push(sum * 10 + node->left->val);
            }
            
            //push node->right to nodeQ
            //and push it's corresponding value to sumQ 
            if (node->right)
            {
                nodeQ.push(node->right);
                sumQ.push(sum * 10 + node->right->val);
            }
        }
        return totalSum;
    }
};